题解：AT_abc443_f [ABC443F] Non-Increasing Number

这题好像根本不难。

假如我们对于一个数确定了它模 $n$ 的余数 $i$，和它的最后一位 $j$，那么这个数的长度一定越短越好。

所以我们可以考虑记录每个状态 $(i, j)$ 可以到达的最短长度，一个一个数字的往后面拼，假如我们拼数字 $k$，那么 $((i \times 10 + k) \% n, k)$ 这个状态的步数就是 $(i, j)$ 的步数加 $1$。

那直接 BFS 这题就做完了，因为每一次我们可以在扩展的时候拼尽量小的数，所以找到的第一个模 $n$ 余数位 $0$ 的状态就是我们想要的答案，我们可以记录每一个状态的前一个状态，一个一个回溯回去就可以得到答案啦。

#include<bits/stdc++.h>
using namespace std;
#define int long long
int dist[3333333][10];
pair<int, int> ls[3333333][10];
signed main()
{
    int n;
    cin >> n;
    queue<pair<int, int>> que;
    que.push({0, 0});
    while (que.size()) {
        int x = que.front().first, y = que.front().second;
        if (x == 0 && y) {
            vector<int> ans;
            while (1) {
                ans.push_back(y);
                if (dist[x][y] == 1) {
                    break;
                }
                auto tp = ls[x][y];
                x = tp.first;
                y = tp.second;
            }
            for (int i = ans.size() - 1; i >= 0; i--) {
                cout << ans[i];
            }
            return 0;
        }
        que.pop();
        for (int i = max(1ll, y); i <= 9; i++) {
            if (dist[(x * 10 + i) % n][i]) {
                continue;
            }
            dist[(x * 10 + i) % n][i] = dist[x][y] + 1;
            que.push({(x * 10 + i) % n, i});
            ls[(x * 10 + i) % n][i] = {x, y};
        }
    }
    cout << -1;
    return 0;
}